<!doctype html>
<html>
	<head>
		<meta charset="utf-8">
		<title>Latency Heatmap</title>
		<meta name="viewport" content="width=device-width, initial-scale=1">

		<link rel="stylesheet" href="../dist/uPlot.min.css">
	</head>
	<body>
		<script src="lib/rand.js"></script>
		<script src="../dist/uPlot.iife.js"></script>
		<script>
			function rawData(xCount, ySeriesCount, yCountMin, yCountMax, yMin, yMax) {
				xCount = xCount || 100;
				ySeriesCount = ySeriesCount || 1;

				// 50-300 samples per x
				yCountMin = yCountMin || 200;
				yCountMax = yCountMax || 500;

				// y values in 0 - 1000 range
				yMin = yMin || 5;
				yMax = yMax || 1000;

				let data = [
					[],
					...Array(ySeriesCount).fill(null).map(_ => []),
				];

				let now = Math.round(new Date() / 1e3);

				let finalCount = 0;

				for (let xi = 0; xi < xCount; xi++) {
					data[0][xi] = now++;

					for (let si = 1; si <= ySeriesCount; si++) {
						let yCount = randInt(yCountMin, yCountMax);

						let vals = data[si][xi] = [];

						while (yCount-- > 0) {
						//	vals.push(Math.round(randn_bm(yMin, yMax, 3)));
							vals.push(Math.max(randomSkewNormal(Math.random, 30, 30, 3), yMin));
							finalCount++;
						}

						vals.sort((a, b) => a - b);
					}
				}

				console.log(finalCount);

				return data;
			}

			const isInt = Number.isInteger;
			const { round, ceil, floor } = Math;

			const fixFloat = v => roundDec(v, 14);

			function incrRound(num, incr) {
				return fixFloat(roundDec(fixFloat(num/incr))*incr);
			}

			function incrRoundUp(num, incr) {
				return fixFloat(ceil(fixFloat(num/incr))*incr);
			}

			function incrRoundDn(num, incr) {
				return fixFloat(floor(fixFloat(num/incr))*incr);
			}

			// https://stackoverflow.com/a/48764436
			// rounds half away from zero
			function roundDec(val, dec = 0) {
				if (isInt(val))
					return val;
			//	else if (dec == 0)
			//		return round(val);

				let p = 10 ** dec;
				let n = (val * p) * (1 + Number.EPSILON);
				return round(n) / p;
			}

			function histogram(vals, bucket, filter, sort) {
				let hist = new Map();

				for (let i = 0; i < vals.length; i++) {
					let v = vals[i];

					if (v != null)
						v = bucket(v);

					let entry = hist.get(v);

					if (entry)
						entry.count++;
					else
						hist.set(v, {value: v, count: 1});
				}

				filter && filter.forEach(v => hist.delete(v));

				let bins = [...hist.values()];

				sort && bins.sort((a, b) => sort(a.value, b.value));

				let values = Array(bins.length);
				let counts = Array(bins.length);

				for (let i = 0; i < bins.length; i++) {
					values[i] = bins[i].value;
					counts[i] = bins[i].count;
				}

				return [
					values,
					counts,
				];
			}

			function aggAll(data, round, filter, sort) {
				let allVals = [].concat(...data[1]);
				return histogram(allVals, round, filter, sort);
			}

			function aggEach(data, round, filter, sort) {
				let data2 = [
					data[0],
					[],
					[],
				];

				data[1].forEach((vals, xi) => {
					let [ bins, counts ] = histogram(vals, round, filter, sort);

					data2[1].push(bins);
					data2[2].push(counts);
				});

				return data2;
			}

			console.time("rawData");
			let raw = rawData();
			console.timeEnd("rawData");
		//	console.log(raw);

			let data = [
				raw[0],
				raw[1].map(vals => vals[0]),
				raw[1].map(vals => vals[vals.length - 1]),
				raw[1],
			];

			function heatmapPlugin() {
				return {
					hooks: {
						draw: u => {
							const { ctx, data } = u;

							let yData = data[3];

							ctx.save()
							ctx.beginPath();
							ctx.rect(u.bbox.left, u.bbox.top, u.bbox.width, u.bbox.height);
							ctx.clip();

							yData.forEach((yVals, xi) => {
								let xPos = Math.round(u.valToPos(data[0][xi], 'x', true));

								yVals.forEach(yVal => {
									let yPos = Math.round(u.valToPos(yVal, 'y', true));
									ctx.fillStyle = "rgba(255,0,0,0.4)";
									ctx.fillRect(
										xPos - 4,
										yPos,
										10,
										1,
									);
								});
							});

							ctx.restore()
						}
					}
				};
			}

			const opts = {
				width: 1800,
				height: 600,
				title: "Latency Heatmap (~35k)",
				plugins: [
					heatmapPlugin(),
				],
				cursor: {
					drag: {
						y: true,
					},
					points: {
						show: false
					}
				},
				series: [
					{},
					{
						paths: () => null,
						points: {show: false},
					},
					{
						paths: () => null,
						points: {show: false},
					},
				],
			};

			let u = new uPlot(opts, data, document.body);


			let bucketIncr = 5;
			let histOffset = 0;
			const histBucket = v => incrRoundDn(v - histOffset, bucketIncr) + histOffset;
			const histFilter = [null];
			const histSort = (a, b) => a - b;

			console.time("aggEach");
			let agg = aggEach(raw, histBucket, histFilter, histSort);
			console.timeEnd("aggEach");

		//	console.log(raw);
		//	console.log(agg);

			let data2 = [
				agg[0],
				raw[1].map(vals => vals[0]),
				raw[1].map(vals => vals[vals.length - 1]),
				agg[1],
				agg[2],
			];

			function heatmapPlugin2() {
				// let global min/max
				function fillStyle(count, minCount, maxCount) {
				//	console.log(val);
					return `hsla(${180 + count/maxCount * 180}, 80%, 50%, 1)`;
				}

				return {
					hooks: {
						draw: u => {
							const { ctx, data } = u;

							let yData = data[3];
							let yQtys = data[4];
/*
							let maxCount = -Infinity;
							let minCount = Infinity;

							yQtys.forEach(qtys => {
								maxCount = Math.max(maxCount, Math.max.apply(null, qtys));
								minCount = Math.min(minCount, Math.min.apply(null, qtys));
							});

							console.log(maxCount, minCount);
*/

							// pre-calc rect height since we know the aggregation bucket
							let yHgt = Math.floor(u.valToPos(bucketIncr, 'y', true) - u.valToPos(0, 'y', true));

							ctx.save()
							ctx.beginPath();
							ctx.rect(u.bbox.left, u.bbox.top, u.bbox.width, u.bbox.height);
							ctx.clip();

							yData.forEach((yVals, xi) => {
								let xPos = Math.floor(u.valToPos(data[0][xi], 'x', true));

								let maxCount = yQtys[xi].reduce((acc, val) => Math.max(val, acc), -Infinity);

								yVals.forEach((yVal, yi) => {
									let yPos = Math.floor(u.valToPos(yVal, 'y', true));

								//	ctx.fillStyle = fillStyle(yQtys[xi][yi], minCount, maxCount);
									ctx.fillStyle = fillStyle(yQtys[xi][yi], 1, maxCount);
									ctx.fillRect(
										xPos - 4,
										yPos,
										10,
										yHgt,
									);
								});
							});

							ctx.restore()
						}
					}
				};
			}

			const opts2 = {
				width: 1800,
				height: 600,
				title: "Latency Heatmap Aggregated 10ms (~20k)",
				plugins: [
					heatmapPlugin2(),
				],
				cursor: {
					drag: {
						y: true,
					},
					points: {
						show: false
					}
				},
				series: [
					{},
					{
						paths: () => null,
						points: {show: false},
					},
					{
						paths: () => null,
						points: {show: false},
					},
				],
			};

			let u2 = new uPlot(opts2, data2, document.body);
		</script>

		<script>
			function heatmap(xs, ys, opts) {
				let xBinIncr = opts.x.binSize;
				let yBinIncr = opts.y.binSize;
				// sortedX?

				let len = xs.length;

				let xSorted = opts.x.sorted ?? false;
				let ySorted = opts.y.sorted ?? false;

				// find x and y limits to pre-compute buckets struct
				let minX = xSorted ? xs[0]       :  Infinity;
				let minY = ySorted ? ys[0]       :  Infinity;
				let maxX = xSorted ? xs[len - 1] : -Infinity;
				let maxY = ySorted ? ys[len - 1] : -Infinity;

				for (let i = 0; i < len; i++) {
					if (!xSorted) {
						minX = Math.min(minX, xs[i]);
						maxX = Math.max(maxX, xs[i]);
					}

					if (!ySorted) {
						minY = Math.min(minY, ys[i]);
						maxY = Math.max(maxY, ys[i]);
					}
				}

				const binX = opts.x.bin;
				const binY = opts.y.bin;

				let minXBin = binX(minX);
				let maxXBin = binX(maxX);
				let minYBin = binY(minY);
				let maxYBin = binY(maxY);

				let xBinQty = (maxXBin - minXBin) / xBinIncr + 1;
				let yBinQty = (maxYBin - minYBin) / yBinIncr + 1;

			/*
				let counts = Array(xBinQty * yBinQty).fill(0);

				for (let i = 0; i < len; i++) {
					if (xs[i] != null && ys[i] != null) {
						let xi = (opts.x.bin(xs[i]) - minXBin) / xBinIncr;
						let yi = (opts.y.bin(ys[i]) - minYBin) / yBinIncr;
						let ci = xi * yBinQty + yi;
						counts[ci]++;
					}
				}
			*/

				let [xs2, ys2, counts] = initHs(xBinQty, yBinQty, minXBin, xBinIncr, minYBin, yBinIncr);

				for (let i = 0; i < len; i++) {
				//	if (xs[i] != null && ys[i] != null) {
						let xi = (binX(xs[i]) - minXBin) / xBinIncr;
						let yi = (binY(ys[i]) - minYBin) / yBinIncr;
						let ci = xi * yBinQty + yi;

						counts[ci]++;
				//	}
				}

				return {
				//	x: {minX, maxX, minXBin, maxXBin, xBinQty},
				//	y: {minY, maxY, minYBin, maxYBin, yBinQty},
					counts,
					xs: xs2,
					ys: ys2,
				};
			}

			function initHs(xQty, yQty, xMin, xIncr, yMin, yIncr) {
				let len = xQty * yQty;
				let xs = Array(len);
				let ys = Array(len);
				let counts = Array(len);

				for (let i = 0, yi = 0, x = xMin; i < len; yi = ++i % yQty) {
					counts[i] = 0;
					ys[i] = yMin + yi * yIncr;

					if (yi == 0 && i >= yQty)
						x += xIncr;

					xs[i] = x;
				}

				return [xs, ys, counts];
			}

		/*
			setInterval(() => {
				console.time("a");
				let h = initHs(300, 150, 1642711320000, 15000, -22, 2);
				console.timeEnd("a");
			}, 500);
		*/

			function heatmapPaths(opts) {
				const { disp } = opts;

				return (u, seriesIdx, idx0, idx1) => {
					uPlot.orient(u, seriesIdx, (series, dataX, dataY, scaleX, scaleY, valToPosX, valToPosY, xOff, yOff, xDim, yDim, moveTo, lineTo, rect, arc) => {
						let d = u.data[seriesIdx];
						let [xs, ys, counts] = d;
						let dlen = xs.length;

						// fill colors are mapped from interpolating densities / counts along some gradient
						// (should be quantized to 64 colors/levels max. e.g. 16)
						let fills = disp.fill.values(u, seriesIdx);

					//	let fillPaths = new Map(); // #rgba => Path2D

						let fillPalette = disp.fill.lookup ?? [...new Set(fills)];

						let fillPaths = fillPalette.map(color => new Path2D());

						// fillPalette.forEach(fill => {
						// 	fillPaths.set(fill, new Path2D());
						// });

						// detect x and y bin qtys by detecting layout repetition in x & y data
						let yBinQty = dlen - ys.lastIndexOf(ys[0]);
						let xBinQty = dlen / yBinQty;
						let yBinIncr = ys[1] - ys[0];
						let xBinIncr = xs[yBinQty] - xs[0];

						// uniform tile sizes based on zoom level
						let xSize = valToPosX(xBinIncr, scaleX, xDim, xOff) - valToPosX(0, scaleX, xDim, xOff);
						let ySize = valToPosY(yBinIncr, scaleY, yDim, yOff) - valToPosY(0, scaleY, yDim, yOff);

						// pre-compute x and y offsets
						let cys = ys.slice(0, yBinQty).map(y => Math.round(valToPosY(y, scaleY, yDim, yOff) - ySize/2));
						let cxs = Array.from({length: xBinQty}, (v, i) => Math.round(valToPosX(xs[i * yBinQty], scaleX, xDim, xOff) - xSize/2));

						for (let i = 0; i < dlen; i++) {
							// filter out 0 counts and out of view
							if (
								counts[i] > 0 &&
								xs[i] >= scaleX.min && xs[i] <= scaleX.max &&
								ys[i] >= scaleY.min && ys[i] <= scaleY.max
							) {
								let cx = cxs[~~(i / yBinQty)];
								let cy = cys[i % yBinQty];

							//	let fillPath = fillPaths.get(fills[i]);
							//	let fillPath = fillPaths.get(fillIndex[fills[i]]);

								let fillPath = fillPaths[fills[i]];

								rect(fillPath, cx, cy, xSize, ySize);

							/*
								qt.add({
									x: cx - size - u.bbox.left,
									y: cy - size - u.bbox.top,
									w: size * 2,
									h: size * 2,
									sidx: seriesIdx,
									didx: i
								});
							*/
							}
						}

						u.ctx.save();
					//	u.ctx.globalAlpha = 0.8;
						u.ctx.rect(u.bbox.left, u.bbox.top, u.bbox.width, u.bbox.height);
						u.ctx.clip();
						// fillPaths.forEach((p, rgba) => {
						// 	u.ctx.fillStyle = rgba;
						// 	u.ctx.fill(p);
						// });
						fillPaths.forEach((p, i) => {
							u.ctx.fillStyle = fillPalette[i];
							u.ctx.fill(p);
						});
						u.ctx.restore();
					});
				};
			}

			// 16-color gradient (white -> orange -> red -> purple)
			const gradMetal16 = [
				"rgb(131,58,180)",
				"rgb(154,65,159)",
				"rgb(178,67,136)",
				"rgb(202,63,111)",
				"rgb(228,53,80)",
				"rgb(253,29,29)",
				"rgb(255,76,37)",
				"rgb(256,106,45)",
				"rgb(256,131,53)",
				"rgb(255,154,61)",
				"rgb(252,176,69)",
				"rgb(254,193,115)",
				"rgb(255,209,153)",
				"rgb(256,224,188)",
				"rgb(256,240,222)",
			//	"rgb(255,255,255)",
			].reverse();

			let palette = gradMetal16;

			const countsToFills = (u, seriesIdx) => {
				let counts = u.data[seriesIdx][2];

				// TODO: integrate 1e-9 hideThreshold?
				const hideThreshold = 0;

				let minCount = Infinity;
				let maxCount = -Infinity;

				for (let i = 0; i < counts.length; i++) {
					if (counts[i] > hideThreshold) {
						minCount = Math.min(minCount, counts[i]);
						maxCount = Math.max(maxCount, counts[i]);
					}
				}

				let range = maxCount - minCount;

				let paletteSize = palette.length;

				let indexedFills = Array(counts.length);

				for (let i = 0; i < counts.length; i++)
					indexedFills[i] = counts[i] === 0 ? -1 : Math.min(paletteSize - 1, Math.floor((paletteSize * (counts[i] - minCount)) / range));

				return indexedFills;
			};

			let opts5 = {
				width: 1800,
				height: 600,
				title: "Heatmap / Scatter (mode: 2) / ~45k",
				mode: 2,
				ms: 1,
				scales: {
					x: {
						time: true,
					}
				},
				series: [
					{},
					{
						label: "Latency",
						paths: heatmapPaths({
							disp: {
								fill: {
									lookup: gradMetal16,
									values: countsToFills
								}
							}
						}),
						facets: [
							{
								scale: 'x',
								auto: true,
								sorted: 1,
							},
							{
								scale: 'y',
								auto: true,
							},
						],
					},
				],
			};


			let xBinIncr = 15e3;
			let yBinIncr = 2;

			// TODO: log10, log2, log32
			let hopts = {
				x: {
					binSize: xBinIncr,
					bin: v => incrRoundDn(v, xBinIncr),
					sorted: true,
				},
				y: {
					binSize: yBinIncr,
					bin: v => incrRoundDn(v, yBinIncr)
				},
			};

			function genData(len = 45e3) {
			//	console.time("genData");
				let now = Date.now();
				let xs = Array(len);
				let ys = Array(len);

				for (let i = 0; i < len; i++) {
					xs[len - 1 - i] = now - i * 100;
					ys[i] = randomSkewNormal(Math.random, 30, 50, 3);
				}

			//	console.timeEnd("genData");

			//	console.time("heatmap");
				let hm = heatmap(xs, ys, hopts);
			//	console.timeEnd("heatmap");

				return [
					hm.xs, // x0
					hm.ys, // y0
					hm.counts, // counts
				//	[1,2,3], // x1
				//	[1,2,3], // y1
					// xSize, ySize // single value implies uniform. in px? disp.size?
				];
			}

			let u5 = new uPlot(opts5, [null, genData()], document.body);

			// setInterval(() => {
			// 	let d = [null, genData()];

			// //	console.time("render");
			// 	u5.setData(d);
			// //	queueMicrotask(() => { console.timeEnd("render"); });
			// }, 1000);
		</script>

		<br>
		<br>
		Bucket size: <input id="binsize" type="range" min="1", max="25" step="1" value="5">
		<span id="cursize">5</span>
		<br>
		Bucket offset: <input id="binoffset" type="range" min="0", max="25" step="1" value="0">
		<span id="curoffset">0</span>

		<script>
			let bars = uPlot.paths.bars({align: 1, size: [1, Infinity], gap: 0});

			const opts3 = {
				width: 1800,
				height: 600,
				title: "Latency Histogram (align: 1, gap: 0, stroke: 2, border collapse)",
				scales: {
					x: {
						time: false,
						auto: false,
						dir: 1,
						range: (u) => [
							u.data[0][0],
							u.data[0][u.data[0].length - 1] + bucketIncr,
						]
					}
				},
				axes: [
					{
						incrs: () => [0,1,2,3,4,5,6,7,8,9,10].map(mult => mult * bucketIncr),
					//	space: 0,
						splits: (u, axisIdx, scaleMin, scaleMax, foundIncr, foundSpace) => {
							let minSpace = u.axes[axisIdx]._space;
							let bucketWidth = u.valToPos(u.data[0][0] + bucketIncr, 'x') - u.valToPos(u.data[0][0], 'x');

							let firstSplit = u.data[0][0];
							let lastSplit = u.data[0][u.data[0].length - 1] + bucketIncr;

							let splits = [];
							let skip = Math.ceil(minSpace / bucketWidth);

							for (let i = 0, s = firstSplit; s <= lastSplit; i++, s += bucketIncr)
								!(i % skip) && splits.push(s);

							return splits;
						},
					}
				],
				series: [
					{},
					{
						paths: bars,
						points: {
							show: false,
						},
						fill: "rgba(255,0,0,0.4)",
						stroke: "rgba(255,0,0,1)",
						width: 2,
					},
				],
			};

			console.time("aggAll");
			let hist = aggAll(raw, histBucket, histFilter, histSort);
			console.timeEnd("aggAll");

			let u3 = new uPlot(opts3, hist, document.body);

			let curSizeEl = document.getElementById("cursize");

			document.getElementById("binsize").oninput = e => {
				bucketIncr = +e.target.value;
				curSizeEl.textContent = bucketIncr;

				console.time("aggAll");
				hist = aggAll(raw, histBucket, histFilter, histSort);
				console.timeEnd("aggAll");

				u3.setData(hist);
			};

			let curOffsetEl = document.getElementById("curoffset");

			document.getElementById("binoffset").oninput = e => {
				histOffset = +e.target.value;
				curOffsetEl.textContent = histOffset;

				console.time("aggAll");
				hist = aggAll(raw, histBucket, histFilter, histSort);
				console.timeEnd("aggAll");

				u3.setData(hist);
			};

			{
				let gap = 3;
				let bars = uPlot.paths.bars({
					size: [1, Infinity],
					gap,

					disp: {
						x0: {
							unit: 1,
							values: (u, seriesIdx, idx0, idx1) => {
								let xData = u.data[0];
								let x0Val = xData[0];
								let gapDelta = u.posToVal(gap, 'x') - x0Val;
								return xData.map(v => v + gapDelta / 2);
							}
						},
						size: {
							unit: 1,
							values: (u, seriesIdx, idx0, idx1) => {
								let xData = u.data[0];
								let size = xData[1] - xData[0];
								return Array(xData.length).fill(size);
							}
						}
					}
				});

				const opts3 = {
					width: 1800,
					height: 600,
					title: "Latency Histogram (align: 1, gap: 2, stroke: 1, disp-gap-shift)",
					scales: {
						x: {
							time: false,
							auto: false,
							dir: 1,
							range: (u) => [
								u.data[0][0],
								u.data[0][u.data[0].length - 1] + bucketIncr,
							]
						}
					},
					axes: [
						{
							grid: {
								show: false,
							},
							incrs: () => [0,1,2,3,4,5,6,7,8,9,10].map(mult => mult * bucketIncr),
						//	space: 0,
							splits: (u, axisIdx, scaleMin, scaleMax, foundIncr, foundSpace) => {
								let minSpace = u.axes[axisIdx]._space;
								let bucketWidth = u.valToPos(u.data[0][0] + bucketIncr, 'x') - u.valToPos(u.data[0][0], 'x');

								let firstSplit = u.data[0][0];
								let lastSplit = u.data[0][u.data[0].length - 1] + bucketIncr;

								let splits = [];
								let skip = Math.ceil(minSpace / bucketWidth);

								for (let i = 0, s = firstSplit; s <= lastSplit; i++, s += bucketIncr)
									!(i % skip) && splits.push(s);

								return splits;
							},
						}
					],
					series: [
						{},
						{
							paths: bars,
							fill: "rgba(255,0,0,0.4)",
							stroke: "rgba(255,0,0,1)",
							points: {
								show: false,
							},
							width: 1,
						},
					],
				};

				new uPlot(opts3, hist, document.body);
			}
		</script>
	</body>
</html>